/*
	解法：排序数组做预处理 + 双指针法
	为什么：参考官方题解
	时间复杂度：O(n²)，空间复杂度：O(log n) + O(k), sort + res所用空间
 */

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution
{
public:
	vector<vector<int>> threeSum(vector<int>& nums)
	{
		int n = nums.size();
		sort(nums.begin(), nums.end());
		vector<vector<int>> res;
		
		// 枚举 a
		for (int first = 0; first < n; ++first)
		{
			// 需要和上一次枚举的a不相同，目的：去重
			if (first > 0 && nums[first] == nums[first - 1])
			{
				continue;
			}
			
			// c 对应的指针初始指向数组的最右端
			int third = n - 1;
			int target = -nums[first];
			
			// 枚举 b
			for (int second = first + 1; second < n; ++second)
			{
				// 需要和上一次枚举的b不相同，目的：去重
				if (second > first + 1 && nums[second] == nums[second - 1])
				{
					continue;
				}
				
				// 需要保证 b 的指针在 c 的指针的左侧
				while (second < third && nums[second] + nums[third] > target)
				{
					--third;
				}
				
				// 如果指针重合，随着 b 后续的增加
				// 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
				if (second == third)
				{
					break;
				}
				
				if (nums[second] + nums[third] == target)
				{
					res.push_back({nums[first], nums[second], nums[third]});
				}
			}
		}
		
		return res;
	}
};

int main() 
{
	vector<int> nums;
	int n, val;
	
	cout << "请输入数组长度: ";
	cin >> n;
	
	cout << "请输入数组元素（空格分隔）: ";
	for (int i = 0; i < n; i++) 
	{
		cin >> val;
		nums.push_back(val);
	}
	
	Solution s;
	vector<vector<int> > result = s.threeSum(nums);
	
	cout << "满足条件的三元组有:" << endl;
	
	for (int i = 0; i < (int)result.size(); i++) 
	{
		cout << "[";
		for (int j = 0; j < (int)result[i].size(); j++) 
		{
			cout << result[i][j];
			if (j < (int)(result[i].size() - 1)) 
			{
				cout << ", ";
			}
		}
		cout << "]" << endl;
	}
	
	return 0;
}


